# 120. 三角形最小路径和
from typing import List


# 给定一个三角形 triangle ，找出自顶向下的最小路径和。
# 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
# 也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

# 时间复杂度：O(n^2)，其中 n 是三角形的行数。
# 空间复杂度：O(n^2)。我们需要一个 n*n 的二维数组存放所有的状态。
def minimumTotal(triangle: List[List[int]]) -> int:
    dp = [triangle[0]]
    for dp_index in range(1, len(triangle)):
        # 上一层dp
        last_level_dp = dp[dp_index - 1]
        # 当前层
        cur_level = triangle[dp_index]
        level_dp = list()
        for level_index in range(len(cur_level)):
            # 当前的数
            cur_num = cur_level[level_index]
            if level_index == 0:
                min_num = last_level_dp[0]
            elif level_index == len(cur_level) - 1:
                min_num = last_level_dp[-1]
            else:
                # 上一层的数
                left = last_level_dp[level_index - 1]
                right = last_level_dp[level_index]
                min_num = min(left, right)

            level_dp.append(min_num + cur_num)

        dp.append(level_dp)

    return min(dp[len(triangle) - 1])


triangle_1 = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
result = minimumTotal(triangle_1)
print(f"result:{result}")

triangle_1 = [[-10]]
result = minimumTotal(triangle_1)
print(f"result:{result}")

triangle_1 = [[-1], [3, 2], [-3, 1, -1]]
result = minimumTotal(triangle_1)
print(f"result:{result}")
